package airthmetic.exercise.sort;

import java.util.Random;

public class _215_数组中的第K个最大元素 {
    public int findKthLargest(int[] nums, int k) {
        int right = nums.length - 1;
        int left = 0;
        int targetIndex = nums.length - k;

        while(true){
            int parIndex = partition2(nums,left,right);
            if(parIndex == targetIndex){
                break;
            }else if(parIndex > targetIndex){
                right = parIndex - 1;
            }else{
                left = parIndex + 1;
            }
        }

        return nums[targetIndex];

    }


    public int partition2(int[] nums, int left, int right){
        int pivotIndex = new Random().nextInt(right - left + 1) + left;
        swap(nums,pivotIndex,left);
        int pivot = nums[left];
        int i = left + 1;
        int j = right;
        while(true){
            // 当i指针还小于等于最右侧 并且i指针的元素小于标杆 那么他就应该在左侧 所以i++
            while (i<=right && nums[i] < pivot){
                i++;
            }
            // 当j指针还大于left(不能是大于等于，因为left上放着的是标杆) 并且j指针大于标杆 那么他就应该在右侧 所以j--
            while (j>left && nums[j] > pivot){
                j--;
            }
            // 左指针大于等于右指针结束循环
            if (i >= j){
                break;
            }

            swap(nums,i++,j--);
        }

        swap(nums,left,j);
        return j;
    }


    public void swap(int[] nums, int i, int j){
        if(i == j){
            return;
        }
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}
